package com.lw.leetcode.dp.c;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 1125. 最小的必要团队
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/19 17:04
 */
public class SmallestSufficientTeam {

    public static void main(String[] args) {
        SmallestSufficientTeam test = new SmallestSufficientTeam();

        // [0,2]
        String[] arr = {"java", "nodejs", "reactjs"};
        List<List<String>> people = new ArrayList<>();

        people.add(Arrays.asList("java"));
        people.add(Arrays.asList("nodejs"));
        people.add(Arrays.asList("nodejs", "reactjs"));

        int[] ints = test.smallestSufficientTeam(arr, people);
        System.out.println(Arrays.toString(ints));
    }


    public int[] smallestSufficientTeam(String[] reqs, List<List<String>> people) {
        Map<String, Integer> map = new HashMap<>();
        int length = reqs.length;
        for (int i = 0; i < length; i++) {
            map.put(reqs[i], i);
        }
        int m = people.size();
        int[] items = new int[m];
        for (int i = 0; i < m; i++) {
            List<String> list = people.get(i);
            int item = 0;
            for (String s : list) {
                item |= (1 << map.get(s));
            }
            items[i] = item;
        }
        int n = 1 << length;
        long[][] arr = new long[m][n];
        int f = 128;
        int fs = (f << 16) + 1;
        long count;
        int item = items[0];
        arr[0][item] = fs;
        for (int i = 0; i < m - 1; i++) {
            item = items[i + 1];
            long[] as = arr[i];
            long[] bs = arr[i + 1];
            bs[item] = fs + ((i + 1) << 8);
            for (int j = 1; j < n; j++) {
                if (as[j] == 0) {
                    continue;
                }
                count = (as[j] & 0XFF);
                int k = j;
                long b = bs[k];
                if (b == 0 || (b & 0XFF) > count) {
                    bs[k] = as[j];
                }
                count++;
                k = item | j;
                b = bs[k];
                if (b == 0 || (b & 0XFF) > count) {
                    bs[k] = ((i + 1) << 8) + ((as[j] & 0XFF00) << 8) + count + ((long) j << 32);
                }
            }
        }
        long v = arr[m - 1][n - 1];
        int a = (int) ((v >> 16) & 0XFF);
        int b = (int) (v & 0XFF);
        int c = (int) ((v >> 8) & 0XFF);
        int d = (int) (v >> 32);
        int[] values = new int[b];
        int index = 0;
        while (a != f) {
            values[index++] = c;
            v = arr[a][d];
            a = (int) ((v >> 16) & 0XFF);
            c = (int) ((v >> 8) & 0XFF);
            d = (int) (v >> 32);
        }
        values[index++] = c;
        return values;
    }

}
